import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;


// find a solution to the initial board (using the A* algorithm)
public class Solver {
	
	private class Node {
		Board current;
		int manhattan;
		int moves;
		int priority;

		public Node(Board current, int moves) {
			this.current = current;
			this.manhattan = current.manhattan();
			this.moves = moves;
			this.priority = this.manhattan + this.moves; 
		}

		@Override
		public String toString() {
			return "Node [current=" + current + ", manhattan=" + manhattan
					+ ", moves=" + moves + ", priority=" + priority + "]";
		}
	}
	
	private class ManhattanComparator implements Comparator<Node> {

		@Override
		public int compare(Node o1, Node o2) {
			
			if (o1.priority > o2.priority) {
				return 1;
			} else if( o1.priority < o2.priority) {
				return -1;
			} else {
				return 0;
			}
		}
		
	}
	
	private List<Board> solution = new ArrayList<Board>();
	private MinPQ<Node> pq = new MinPQ<Node>(new ManhattanComparator());
	private MinPQ<Node> twinpq = new MinPQ<Node>(new ManhattanComparator());
	private boolean solvable = true;
	private Board previous = null;
	private Board previousTwin = null;
	private int movesCount = 0;
	

	public Solver(Board initial) {
		if ( ! initial.isGoal()) {
			solve(initial);
		}
    }

	private void solve(Board initial) {

		solution.add(initial);

		Node n = new Node(initial, 0);
		pq.insert(n);
		Node twin = new Node(initial.twin(), 0);
		twinpq.insert(twin);
		
		do {
			previous = n.current;
			previousTwin = twin.current;
			n = pq.delMin();
			twin = twinpq.delMin();
			solution.add(n.current);
			Iterable<Board> neighbors = n.current.neighbors();
			for (Board board : neighbors) {
				if ( ! board.equals(previous)) {
					Node node = new Node(board,n.moves+1);
					pq.insert(node);
				}
			}
			
			Iterable<Board> twinneighbors = twin.current.neighbors();
			for (Board board : twinneighbors) {
				if ( ! board.equals(previousTwin)) {
					Node node = new Node(board,twin.moves+1);
					twinpq.insert(node);
				}
			}
			
		} while (!n.current.isGoal() && !twin.current.isGoal());
		if (twin.current.isGoal()) {
			solvable = false;
			solution.clear();
		} else {
			movesCount = n.moves;
		}
	}

    public boolean isSolvable(){
    	return solvable;
    }
    
    // min number of moves to solve initial board; -1 if no solution
    public int moves(){
    	if (solvable) {
    		return movesCount;
    	} else {
    		return -1; 
    	}
    }
    
    // sequence of boards in a shortest solution; null if no solution
    public Iterable<Board> solution() {
    	if (solvable) {
    		return solution;
    	} else {
    		return null; 
    	}
    }
    
    public static void main(String[] args) throws CloneNotSupportedException {
     	In in = new In("C:\\Users\\kris\\Desktop\\Algorithms\\8puzzle\\puzzle30.txt");
        int N = in.readInt();
        int[][] blocks = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                blocks[i][j] = in.readInt();
        Board initial = new Board(blocks);
        
        Stopwatch s = new Stopwatch();
        Solver solver = new Solver(initial);
        double elapsedTime = s.elapsedTime();
        if (!solver.isSolvable()){
        	StdOut.println("No solution possible");
        }
        else {
            for (Board board : solver.solution()) {
            	StdOut.println(board);
            }
            StdOut.println("Minimum number of moves = " + solver.moves());
            StdOut.println("Elapsed time = " + elapsedTime);
        }
    }
}